#pragma once
#include <iostream>

namespace my_bst
{
    template <typename K, typename V>
    struct BSTNode
    {
        BSTNode(const K &key, const V &val)
            : _key(key),
              _val(val),
              _left(nullptr),
              _right(nullptr)
        {
        }
        K _key;
        V _val;
        BSTNode *_left;
        BSTNode *_right;
    };

    template <typename K, typename V>
    class BST
    {
        typedef BSTNode<K, V> Node;
        typedef BST<K, V> Self;

    private:
        Node *get_node(const K &key, const V &val)
        {
            return new Node(key, val);
        }
        Node *_copy(Node *root)
        {
            if (root == nullptr)
                return nullptr;
            Node *node = get_node(root->_key, root->_val);
            node->_left = _copy(root->_left);
            node->_right = _copy(root->_right);
            return node;
        }
        void _destroy(Node *root)
        {
            if (root == nullptr)
                return;
            _destroy(root->_left);
            _destroy(root->_right);
            delete root;
            root = nullptr;
        }
        void _InOrder(Node *root)
        {
            if (root == nullptr)
                return;
            _InOrder(root->_left);
            std::cout << root->_val << " ";
            _InOrder(root->_right);
        }

    public:
        void InOrder()
        {
            _InOrder(_root);
            std::cout << std::endl;
        }
        BST()
            : _root(nullptr)
        {
        }

        BST(const Self &bst)
        {
            _root = _copy(bst._root);
        }
        ~BST()
        {
            _destroy(_root);
        }

        void swap(Self &bst)
        {
            std::swap(_root, bst._root);
        }

        BST(Self &&bst)
        {
            swap(bst);
        }
        Self &operator=(const Self &bst)
        {
            _root = _copy(bst._root);
        }

        bool insert(const K &key, const V &val)
        {
            if (_root == nullptr)
            {
                _root = get_node(key, val);
                return true;
            }
            Node *cur = _root;
            Node *parent = cur;

            while (cur)
            {
                parent = cur;
                if (key > cur->_key)
                    cur = cur->_right;
                else if (key < cur->_key)
                    cur = cur->_left;
                else
                    return false;
            }
            Node *node = get_node(key, val);
            if (key > parent->_key)
                parent->_right = node;
            else
                parent->_left = node;
            return true;
        }
        Node *find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (key > cur->_key)
                    cur = cur->right;
                else if (key < cur->_key)
                    cur = cur->_left;
                else
                    return cur;
            }
            return nullptr;
        }
        // 删除某个节点，需要去这个节点的左子树中找最大值 或者 去这个节点的右子树中找最小值
        // 重新作为删除的节点
        // 如果删除的节点是_root 需要重新跟新root
        // 如果左子树不存在就找右子树
        bool earse(const K &key)
        {
            Node *parent = _root;
            Node *cur = _root;
            while (cur)
            {

                // parent = cur;

                // cur走了 父节点才得更新！不能放在外面
                // 如果key == cur时 parent放外面也会更新
                if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {

                    Node *left = nullptr;
                    Node *right = nullptr;
                    Node *dparent = cur; // 新节点的父节点
                    // 找删除节点左子树的最大节点
                    // 左子树存在找左子树的最大值
                    if (cur->_left)
                    {
                        left = cur->_left;
                        if (left->_right) // 如果其存在右子树
                        {
                            while (left->_right)
                            {
                                dparent = left;
                                left = left->_right;
                            }
                            dparent->_right = nullptr;
                        }
                        else // 不存在右子树,left即为最大值
                        {
                            ;
                        }
                    } // 如果左子树不存在就找右子树的最小值
                    else if (cur->_right)
                    {
                        right = cur->_right;
                        if (right->_left) // 如果其存在左子树
                        {
                            while (right->_left)
                            {
                                dparent = right;
                                right = right->_left;
                            }
                            dparent->_left = nullptr;
                        }
                        else // 不存在左子树，right即为最小值
                        {
                            ;
                        }
                    }

                    Node *newnode = left ? left : right;
                    if (newnode) // cur不是叶子节点的情况
                    {
                        if (cur == _root) // 删除节点是根节点
                        {
                            _root = newnode;
                        }
                        else
                        {
                            // 删除节点的父亲节点连接该新节点
                            // cur的parent 连接 newnode
                            if (newnode->_key > parent->_key)
                                parent->_right = newnode;
                            else
                                parent->_left = newnode;
                        }
                        // 新的节点还需要和 删除节点的左右子树建立连接
                        // 新节点不能是删除节点本身的左孩子，有孩子在
                        if (cur->_left != newnode)
                            newnode->_left = cur->_left;
                        if (cur->_right != newnode)
                            newnode->_right = cur->_right;
                    }
                    else // newnode为空,cur是叶子节点的情况
                    {
                        // 叶子节点的父亲需要指向nullptr
                        if (cur->_key > parent->_key)
                            parent->_right = nullptr;
                        else
                            parent->_left = nullptr;
                    }
                    delete cur;
                    cur = nullptr;
                    return true;
                }
            }
            return false;
        }

        // 另一种删除 替换法
        // 思路更加的清晰
        bool earse2(const K& key)
        {
            Node* parent = _root;
            Node* cur = _root;
            while (cur)
            {
                if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    // 删除节点cur的3种情况
                    if (cur->_left == nullptr) // 右子树不为空 or 空，左子树为空
                    {
                        if (parent->_left == cur)
                            parent->_left = cur->_right;
                        else
                            parent->_right = cur->_right;
                        delete cur;
                        cur = nullptr;
                        return true;
                    }
                    else if (cur->_right == nullptr) // 左子树不为空 or 空，右子树为空
                    {
                        if (parent->_left == cur)
                            parent->_left = cur->_left;
                        else
                            parent->_right = cur->_left;
                        delete cur;
                        cur = nullptr;
                        return true;

                    }
                    else // 左右子树都不为空
                    {
                        // 找删除节点左子树中的最大值 or 找删除节点右子树中的最小值
                        // 我们找左子树中的最大值
                        // 
                        // 删除并不真删除，我们采用替换的方法。
                        // 将节点中的key,val 进行交换即可
                        // 删除最值节点
                        Node* left = cur->_left;
                        Node* pleft = cur;
                        while (left->_right)
                        {
                            pleft = left;
                            left = left->_right;
                        }
                        cur->_key = left->_key;
                        cur->_val = left->_val;
                        // 该最大值节点可能存在左子树，但一定不存在右子树
                        // 我们要托孤
                        
                        // 最值节点存在两种情况
                        // 1.是cur的左孩子，其不存在右子树
                        if (left == pleft->_left)
                            pleft->_left = left->_left;
                        else // 2. 是cur左孩子上，右子树中的最大值
                            pleft->_right = left->_left;

                        delete left;
                        left = nullptr;
                        return true;
                    }   
                }
            }
            return false;
        }

    private:
        Node *_root = nullptr;
    };
}